/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhongfang
 *
 */
public class nextclosesttime {
	public String nextClosestTime(String time) {
		int[] timeSorted = new int[4];
		int[] timeInt = new int[4];
		int j = 0;
		for (int i = 0; i < time.length(); i++) {
			if (i == 2) {
				continue;
			}
			int tmp = time.charAt(i) - '0';
			timeSorted[j] = tmp;
			timeInt[j] = tmp;
			j++;
		}
		Arrays.sort(timeSorted);
		// 先找比它大的且最小的
		for (int i = 3; i >= 0; i--) {
			int cur = timeInt[i];
			int index = Arrays.binarySearch(timeSorted, cur);
			// 尝试用比它大的构造合法的时间
			index++;
			// 有可能有重复值，所以要一直加到不同
			while (index < 4 && timeSorted[index] == cur) {
				index++;
			}
			if (index == 4) {
				timeInt[i] = timeSorted[0];// 把当前值改成最小值
				continue;
			}
			int tmp = timeSorted[index];
			if (i < 2) {// 小时
				int clock = 0;
				if (i == 1) {
					clock += ((timeInt[0]) * 10 + tmp);
				} else {
					clock += (tmp * 10 + timeInt[1]);
				}
				if (clock < 24) {
					String string = "";
					if (clock < 10) {
						string = "0" + clock;
					} else {
						string += clock;
					}
					return string + ":" + timeInt[2] + timeInt[3];
				}
			} else {// 分钟
				int minu = 0;
				if (i == 2) {
					minu += (tmp * 10 + (timeInt[3]));
				} else {
					minu += ((timeInt[2]) * 10 + tmp);
				}
				if (minu < 60) {
					String string = "";
					if (minu < 10) {
						string = "0" + minu;
					} else {
						string += minu;
					}
					return "" + timeInt[0] + timeInt[1] + ":" + string;
				}
			}
			timeInt[i] = timeSorted[0];// 把当前值改成最小值
		}
		// 再找最小的合法时间
		return "" + timeSorted[0] + timeSorted[0] + ":" + timeSorted[0] + timeSorted[0];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String time = "01:37";
		System.out.println(new nextclosesttime().nextClosestTime(time));
	}
}
